#pragma once

#include <list>
#include <unordered_map>

using std::pair;
using std::list;
using std::unordered_map;

class LRUCache
{
    typedef list<pair<int, int>>::iterator Iter;
public:
    LRUCache(int capacity)
        : _capa(capacity)
        {}
    
    void update(Iter it)
    {
        _cache.splice(_cache.end(), _cache, it);
    }

    int get(int key)
    {
        auto it2 = _hashMap.find(key);
        if(it2 == _hashMap.end()) return -1;

        update(it2->second);

        return it2->second->second;
    }
    
    void put(int key, int value)
    {
        auto it2 = _hashMap.find(key);
        if(it2 != _hashMap.end())
        {
            it2->second->second = value;
            update(it2->second);
        }
        else
        {
            if(_cache.size() == _capa)
            {
                int lastKey = _cache.begin()->first;
                _hashMap.erase(lastKey);
                _cache.pop_front();
            } 
            _cache.push_back( {key,value} );
            _hashMap.insert( {key,--_cache.end()} );
        }
    }
private:
    unordered_map<int, Iter> _hashMap;
    list<pair<int, int>> _cache;
    int _capa;
};